package easy;

/**
 * @author admin
 * 942. 增减字符串匹配
 * 解题思路：定义两个变量，一个用来保存最低位，一个用来保存最高位，
 * 即数组长度。然后对字符串进行遍历，当遇到I时，就把low添加到数组
 * 对应的位置，然后减1，但遇到D时，就把high放入对应的位置，并减1，
 * 最后把high或者low加入数组的最后一位（此时high和low是相同的），
 * 此时就可以保证如果 S[i] == "I"，那么 A[i] < A[i+1]，如果
 * S[i] == "D"，那么 A[i] > A[i+1]
 */
public class LeeCode942 {

    public int[] diStringMatch(String s) {

        int N = s.length();
        int[] res = new int[N + 1];
        int low = 0;
        int high = s.length();
        for (int i = 0; i < N; i++) {
            if (s.charAt(i) == 'I'){
                res[i] = low;
                low++;
            }else {
                res[i] = high;
                high--;
            }
        }
        System.out.println("high:" + high + " low:" + low);
        res[N] = high;
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new LeeCode942().diStringMatch("IDID"));
    }
}
